package random;

import datastructure.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉搜索树节点最小距离（有一个最重要的特点，就是中序遍历后的数组是递增有序的！！！）
 *
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 */

public class L783 {

    public static void main(String[] args) {

        List<Integer> array = new ArrayList<>();
        array.add(1);
        array.add(0);
        array.add(48);
        array.add(null);
        array.add(null);
        array.add(12);
        array.add(49);

        TreeNode treeNode = TreeNode.arrayToTree(array);
        L783 l783 = new L783();
        System.out.println(l783.minDiffInBST(treeNode));
        TreeNode.print(treeNode);

    }

    int temp;
    int ans;
    public int minDiffInBST(TreeNode root) {

        ans = Integer.MAX_VALUE;
        temp = -1;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {

        if (root == null) return;
        dfs(root.getLeft());
        if (temp == -1) {
            temp = root.getVal();
        } else {
            ans = Math.min(ans, root.getVal() - temp);
            temp = root.getVal();
        }
        dfs(root.getRight());

      /*  作者：LeetCode-Solution
        链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/solution/er-cha-sou-suo-shu-jie-dian-zui-xiao-ju-8u87w/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
    }
}
